

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#include "common/utils.hpp"

// 分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了
int getHeight(TreeNode* node) {
    if (node == nullptr) return 0;

    int lHeight = getHeight(node->left);
    if (lHeight == -1) return -1;
    int rHeight = getHeight(node->right);
    if (rHeight == -1) return -1;

    int ret;
    if (std::abs(lHeight - rHeight) > 1) ret = -1;
    else ret = 1 + std::max(lHeight, rHeight);

    return ret;
}

bool isBalanced(TreeNode* root) {
    int h = getHeight(root);
    return h != -1;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> arr = {1,2,2,3,-1,-1,3,4,-1,-1,4};
    TreeNode* root = createTreeNodeByArray(arr);
    printTreeNode(root);
    
    bool res = isBalanced(root);
    std::cout << "res: " << res << "\n";
}